package acwing;

import java.io.*;
import java.util.Arrays;

public class ac849 {
    static final int N = 510;
    static int n, m;
    static int[][] g = new int[N][N];
    static int[] d = new int[N];
    static boolean[] st = new boolean[N];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    static int cin() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int dijkstra() {
        Arrays.fill(d, 0x3f3f3f3f);
        d[1] = 0;
        for (int i = 0; i < n - 1; i ++ ) {
            int t = -1;
            for (int j = 1; j <= n; j ++ ) {
                if (!st[j] && (t == -1 || d[t] > d[j])) t = j;
            }
            for (int j = 1; j <= n; j ++ ) {
                d[j] = Math.min(d[j], d[t] + g[t][j]);
            }
            st[t] = true;
        }
        if (d[n] == 0x3f3f3f3f) return -1;
        return d[n];
    }

    public static void main(String[] args) throws IOException {
        n = cin();
        m = cin();
//        Arrays.fill(g, 0x3f3f3f3f);
        for (int i = 0; i < g.length; i ++ ) Arrays.fill(g[i], 0x3f3f3f3f);
        while (m -- > 0) {
            int x = cin(), y = cin(), z = cin();
            g[x][y] = Math.min(g[x][y], z);
        }
        out.println(dijkstra());
        out.close();
    }
}
